#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <queue>

using namespace std;

//第K大的元素

//朴素排序法
int findKthLargest1(vector<int> &nums, int k)
{
    sort(nums.begin(), nums.end(), greater<int>());
    return nums[k - 1];
}

// heap 大小为K、从小到大的堆，建立之后堆顶 top元素即为第k大的元素
int findKthLargest(vector<int> &nums, int k)
{
    priority_queue<int , vector<int>, greater<int>> pq;
    for(auto &i : nums)
    {
        if(pq.size() >=k && pq.top() > i)
            continue;
        pq.push(i);
        if(pq.size() >k)
            pq.pop();
    }
    return pq.top();
}

int main()
{
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<int> vi(arr, arr + n);
    
    int r = findKthLargest(vi, 2);
    cout << r << endl;
    return 0;
}